package com.yvon.service.demo.algorithm.offer;

/**
 * 给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
 * 单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
 * https://doocs.gitee.io/leetcode/#/lcof/%E9%9D%A2%E8%AF%95%E9%A2%9812.%20%E7%9F%A9%E9%98%B5%E4%B8%AD%E7%9A%84%E8%B7%AF%E5%BE%84/README
 */
public class P12 {

    public static void main(String[] args) {
        Solution solution = new P12().new Solution();
        char[][]board = {{'A','B','C','E'},
                         {'S','F','C','S'},
                         {'A','D','E','E'}};
        String word = "CSEED";
        System.out.println(solution.exist(board, word));
    }

    /**
     *  从board的第一个元素开始查找单词的第一个字母，如果两个字符相同，则继续在该元素的上下左右四个位置寻找单词的下一个字母，如果字符不相同，直接返回false宣告这条路径没有该单词。
     *  查询结束条件为元素越界或者找到单词的最后一个字母
     *  需要一个布尔二维数组 used[][] 用来标记board元素是否已经被查找以避免重复使用。
     *
     * https://blog.csdn.net/weixin_53536363/article/details/123609895
     */
    class Solution {
        public boolean exist(char[][] board, String word) {
            if (board == null || board[0].length == 0 || word =="" || word.length() > board.length * board[0].length) {
                return false;
            }
            boolean[][] mark = new boolean[board.length][board[0].length];
            for (int i = 0; i < board.length; i++) {
                for (int j = 0; j < board[0].length; j++) {
                   if(dfs(board, word, mark, i, j, 0))  {
                       return true;
                   }
                }
            }
            return false;
        }

        /**
         * dfs
         *
         * @param board 网格
         * @param word  单词
         * @param mark  标识已使用的点
         * @param i     一维指针
         * @param j     二维指针
         * @param no    匹配到的单词数
         * @return boolean
         * @author : Yvon / 2022-07-21
         */
        private boolean dfs(char[][] board, String word, boolean[][] mark, int i, int j, int no) {
            // 如果超过边界直接返回
            if (i < 0 || j < 0 || i >= board.length || j >= board[0].length) {
                return false;
            }
            // 如果该点未重复使用过，并且和单词匹配
            if (!mark[i][j] && board[i][j] == word.charAt(no)) {
                // 标记该点为已使用
                mark[i][j] = true;
                // 如果字段已匹配完毕
                if (no == word.length() - 1) {
                    return true;
                } else if (
                        // 继续匹配
                        // 向右
                        dfs(board, word, mark, i, j + 1, no + 1) ||
                                // 下
                                dfs(board, word, mark, i + 1, j, no + 1) ||
                                // 左
                                dfs(board, word, mark, i, j - 1, no + 1) ||
                                // 上
                                dfs(board, word, mark, i - 1, j, no + 1)
                ) {
                    return true;
                }
            }
            return false;
        }


    }
}
